<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta http-equiv="Content-Type" content="text/xhtml;charset=UTF-8"/>
<meta http-equiv="X-UA-Compatible" content="IE=9"/>
<meta name="generator" content="Doxygen 1.8.10"/>
<title>Introduction_to_Algorithms: IntroductionToAlgorithm::SortAlgorithm Namespace Reference</title>
<link href="tabs.css" rel="stylesheet" type="text/css"/>
<script type="text/javascript" src="jquery.js"></script>
<script type="text/javascript" src="dynsections.js"></script>
<link href="navtree.css" rel="stylesheet" type="text/css"/>
<script type="text/javascript" src="resize.js"></script>
<script type="text/javascript" src="navtreedata.js"></script>
<script type="text/javascript" src="navtree.js"></script>
<script type="text/javascript">
  $(document).ready(initResizable);
  $(window).load(resizeHeight);
</script>
<link href="search/search.css" rel="stylesheet" type="text/css"/>
<script type="text/javascript" src="search/searchdata.js"></script>
<script type="text/javascript" src="search/search.js"></script>
<script type="text/javascript">
  $(document).ready(function() { init_search(); });
</script>
<link href="doxygen.css" rel="stylesheet" type="text/css" />
</head>
<body>
<div id="top"><!-- do not remove this div, it is closed by doxygen! -->
<div id="titlearea">
<table cellspacing="0" cellpadding="0">
 <tbody>
 <tr style="height: 56px;">
  <td id="projectalign" style="padding-left: 0.5em;">
   <div id="projectname">Introduction_to_Algorithms
   </div>
  </td>
 </tr>
 </tbody>
</table>
</div>
<!-- end header part -->
<!-- Generated by Doxygen 1.8.10 -->
<script type="text/javascript">
var searchBox = new SearchBox("searchBox", "search",false,'Search');
</script>
  <div id="navrow1" class="tabs">
    <ul class="tablist">
      <li><a href="index.html"><span>Main&#160;Page</span></a></li>
      <li class="current"><a href="namespaces.html"><span>Namespaces</span></a></li>
      <li><a href="annotated.html"><span>Classes</span></a></li>
      <li><a href="files.html"><span>Files</span></a></li>
      <li>
        <div id="MSearchBox" class="MSearchBoxInactive">
        <span class="left">
          <img id="MSearchSelect" src="search/mag_sel.png"
               onmouseover="return searchBox.OnSearchSelectShow()"
               onmouseout="return searchBox.OnSearchSelectHide()"
               alt=""/>
          <input type="text" id="MSearchField" value="Search" accesskey="S"
               onfocus="searchBox.OnSearchFieldFocus(true)" 
               onblur="searchBox.OnSearchFieldFocus(false)" 
               onkeyup="searchBox.OnSearchFieldChange(event)"/>
          </span><span class="right">
            <a id="MSearchClose" href="javascript:searchBox.CloseResultsWindow()"><img id="MSearchCloseImg" border="0" src="search/close.png" alt=""/></a>
          </span>
        </div>
      </li>
    </ul>
  </div>
  <div id="navrow2" class="tabs2">
    <ul class="tablist">
      <li><a href="namespaces.html"><span>Namespace&#160;List</span></a></li>
      <li><a href="namespacemembers.html"><span>Namespace&#160;Members</span></a></li>
    </ul>
  </div>
</div><!-- top -->
<div id="side-nav" class="ui-resizable side-nav-resizable">
  <div id="nav-tree">
    <div id="nav-tree-contents">
      <div id="nav-sync" class="sync"></div>
    </div>
  </div>
  <div id="splitbar" style="-moz-user-select:none;" 
       class="ui-resizable-handle">
  </div>
</div>
<script type="text/javascript">
$(document).ready(function(){initNavTree('namespace_introduction_to_algorithm_1_1_sort_algorithm.html','');});
</script>
<div id="doc-content">
<!-- window showing the filter options -->
<div id="MSearchSelectWindow"
     onmouseover="return searchBox.OnSearchSelectShow()"
     onmouseout="return searchBox.OnSearchSelectHide()"
     onkeydown="return searchBox.OnSearchSelectKey(event)">
</div>

<!-- iframe showing the search results (closed by default) -->
<div id="MSearchResultsWindow">
<iframe src="javascript:void(0)" frameborder="0" 
        name="MSearchResults" id="MSearchResults">
</iframe>
</div>

<div class="header">
  <div class="summary">
<a href="#nested-classes">Classes</a> &#124;
<a href="#func-members">Functions</a>  </div>
  <div class="headertitle">
<div class="title">IntroductionToAlgorithm::SortAlgorithm Namespace Reference</div>  </div>
</div><!--header-->
<div class="contents">

<p>Namespace of <a class="el" href="namespace_introduction_to_algorithm_1_1_sort_algorithm.html" title="Namespace of SortAlgorithm. ">SortAlgorithm</a>.  
<a href="#details">More...</a></p>
<table class="memberdecls">
<tr class="heading"><td colspan="2"><h2 class="groupheader"><a name="nested-classes"></a>
Classes</h2></td></tr>
<tr class="memitem:"><td class="memItemLeft" align="right" valign="top">class &#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="class_introduction_to_algorithm_1_1_sort_algorithm_1_1_sort___heap.html">Sort_Heap</a></td></tr>
<tr class="memdesc:"><td class="mdescLeft">&#160;</td><td class="mdescRight">Sort_Heap：用于堆排序的堆，算法导论第6章  <a href="class_introduction_to_algorithm_1_1_sort_algorithm_1_1_sort___heap.html#details">More...</a><br /></td></tr>
<tr class="separator:"><td class="memSeparator" colspan="2">&#160;</td></tr>
</table><table class="memberdecls">
<tr class="heading"><td colspan="2"><h2 class="groupheader"><a name="func-members"></a>
Functions</h2></td></tr>
<tr class="memitem:a1c3f0138b22c1e0c0bbfa67490ec51f1"><td class="memTemplParams" colspan="2">template&lt;typename Iterator &gt; </td></tr>
<tr class="memitem:a1c3f0138b22c1e0c0bbfa67490ec51f1"><td class="memTemplItemLeft" align="right" valign="top">void&#160;</td><td class="memTemplItemRight" valign="bottom"><a class="el" href="namespace_introduction_to_algorithm_1_1_sort_algorithm.html#a1c3f0138b22c1e0c0bbfa67490ec51f1">bucket_sort</a> (const Iterator begin, const Iterator end, const typename std::iterator_traits&lt; Iterator &gt;::value_type &amp;min_val, const typename std::iterator_traits&lt; Iterator &gt;::value_type &amp;max_val)</td></tr>
<tr class="memdesc:a1c3f0138b22c1e0c0bbfa67490ec51f1"><td class="mdescLeft">&#160;</td><td class="mdescRight">bucket_sort：算法导论第8章 8.4  <a href="#a1c3f0138b22c1e0c0bbfa67490ec51f1">More...</a><br /></td></tr>
<tr class="separator:a1c3f0138b22c1e0c0bbfa67490ec51f1"><td class="memSeparator" colspan="2">&#160;</td></tr>
<tr class="memitem:af51ff6ca75d6dccb1add1ad92a5d32fb"><td class="memTemplParams" colspan="2">template&lt;typename Iterator &gt; </td></tr>
<tr class="memitem:af51ff6ca75d6dccb1add1ad92a5d32fb"><td class="memTemplItemLeft" align="right" valign="top">void&#160;</td><td class="memTemplItemRight" valign="bottom"><a class="el" href="namespace_introduction_to_algorithm_1_1_sort_algorithm.html#af51ff6ca75d6dccb1add1ad92a5d32fb">count_sort</a> (const Iterator begin, const Iterator end, const typename std::iterator_traits&lt; Iterator &gt;::value_type &amp;max_val)</td></tr>
<tr class="memdesc:af51ff6ca75d6dccb1add1ad92a5d32fb"><td class="mdescLeft">&#160;</td><td class="mdescRight">count_sort：算法导论第8章 8.2  <a href="#af51ff6ca75d6dccb1add1ad92a5d32fb">More...</a><br /></td></tr>
<tr class="separator:af51ff6ca75d6dccb1add1ad92a5d32fb"><td class="memSeparator" colspan="2">&#160;</td></tr>
<tr class="memitem:a363c47d6d0dad2f1217b08d355e81126"><td class="memTemplParams" colspan="2">template&lt;typename Iterator , typename CompareType  = std::less&lt;typename std::iterator_traits&lt;Iterator&gt;::value_type&gt;&gt; </td></tr>
<tr class="memitem:a363c47d6d0dad2f1217b08d355e81126"><td class="memTemplItemLeft" align="right" valign="top">void&#160;</td><td class="memTemplItemRight" valign="bottom"><a class="el" href="namespace_introduction_to_algorithm_1_1_sort_algorithm.html#a363c47d6d0dad2f1217b08d355e81126">insert_sort</a> (const Iterator begin, const Iterator end, CompareType compare=CompareType())</td></tr>
<tr class="memdesc:a363c47d6d0dad2f1217b08d355e81126"><td class="mdescLeft">&#160;</td><td class="mdescRight">insert_sort：算法导论第二章 2.1  <a href="#a363c47d6d0dad2f1217b08d355e81126">More...</a><br /></td></tr>
<tr class="separator:a363c47d6d0dad2f1217b08d355e81126"><td class="memSeparator" colspan="2">&#160;</td></tr>
<tr class="memitem:a4806cf41bd25ff1d1344d858a7a5b577"><td class="memTemplParams" colspan="2">template&lt;typename Iterator , typename CompareType  = std::less&lt;typename std::iterator_traits&lt;Iterator&gt;::value_type&gt;&gt; </td></tr>
<tr class="memitem:a4806cf41bd25ff1d1344d858a7a5b577"><td class="memTemplItemLeft" align="right" valign="top">void&#160;</td><td class="memTemplItemRight" valign="bottom"><a class="el" href="namespace_introduction_to_algorithm_1_1_sort_algorithm.html#a4806cf41bd25ff1d1344d858a7a5b577">merge</a> (const Iterator begin, const Iterator end, const Iterator middle, CompareType compare=CompareType())</td></tr>
<tr class="memdesc:a4806cf41bd25ff1d1344d858a7a5b577"><td class="mdescLeft">&#160;</td><td class="mdescRight">merge：算法导论第二章 2.3.1  <a href="#a4806cf41bd25ff1d1344d858a7a5b577">More...</a><br /></td></tr>
<tr class="separator:a4806cf41bd25ff1d1344d858a7a5b577"><td class="memSeparator" colspan="2">&#160;</td></tr>
<tr class="memitem:a38dce6f6996c858aef1096d75bb785db"><td class="memTemplParams" colspan="2">template&lt;typename Iterator , typename CompareType  = std::less&lt;typename std::iterator_traits&lt;Iterator&gt;::value_type&gt;&gt; </td></tr>
<tr class="memitem:a38dce6f6996c858aef1096d75bb785db"><td class="memTemplItemLeft" align="right" valign="top">void&#160;</td><td class="memTemplItemRight" valign="bottom"><a class="el" href="namespace_introduction_to_algorithm_1_1_sort_algorithm.html#a38dce6f6996c858aef1096d75bb785db">merge_sort</a> (const Iterator begin, const Iterator end, CompareType compare=CompareType())</td></tr>
<tr class="memdesc:a38dce6f6996c858aef1096d75bb785db"><td class="mdescLeft">&#160;</td><td class="mdescRight">merge_sort：算法导论第二章 2.3.1  <a href="#a38dce6f6996c858aef1096d75bb785db">More...</a><br /></td></tr>
<tr class="separator:a38dce6f6996c858aef1096d75bb785db"><td class="memSeparator" colspan="2">&#160;</td></tr>
<tr class="memitem:a3a2d13a83cd168d9a10df0ed8c39f9ee"><td class="memTemplParams" colspan="2">template&lt;typename Iterator , typename CompareType  = std::less&lt;typename std::iterator_traits&lt;Iterator&gt;::value_type&gt;&gt; </td></tr>
<tr class="memitem:a3a2d13a83cd168d9a10df0ed8c39f9ee"><td class="memTemplItemLeft" align="right" valign="top">Iterator&#160;</td><td class="memTemplItemRight" valign="bottom"><a class="el" href="namespace_introduction_to_algorithm_1_1_sort_algorithm.html#a3a2d13a83cd168d9a10df0ed8c39f9ee">partition</a> (const Iterator begin, const Iterator end, const Iterator partition_iter, CompareType compare=CompareType())</td></tr>
<tr class="memdesc:a3a2d13a83cd168d9a10df0ed8c39f9ee"><td class="mdescLeft">&#160;</td><td class="mdescRight">partition： 算法导论第7章快速排序中的划分算法  <a href="#a3a2d13a83cd168d9a10df0ed8c39f9ee">More...</a><br /></td></tr>
<tr class="separator:a3a2d13a83cd168d9a10df0ed8c39f9ee"><td class="memSeparator" colspan="2">&#160;</td></tr>
<tr class="memitem:aa304e98b87d7ec1c17bd5cae534fb666"><td class="memTemplParams" colspan="2">template&lt;typename Iterator , typename CompareType  = std::less&lt;typename std::iterator_traits&lt;Iterator&gt;::value_type&gt;&gt; </td></tr>
<tr class="memitem:aa304e98b87d7ec1c17bd5cae534fb666"><td class="memTemplItemLeft" align="right" valign="top">void&#160;</td><td class="memTemplItemRight" valign="bottom"><a class="el" href="namespace_introduction_to_algorithm_1_1_sort_algorithm.html#aa304e98b87d7ec1c17bd5cae534fb666">quick_sort</a> (const Iterator begin, const Iterator end, CompareType compare=CompareType())</td></tr>
<tr class="memdesc:aa304e98b87d7ec1c17bd5cae534fb666"><td class="mdescLeft">&#160;</td><td class="mdescRight">quick_sort： 算法导论第7章  <a href="#aa304e98b87d7ec1c17bd5cae534fb666">More...</a><br /></td></tr>
<tr class="separator:aa304e98b87d7ec1c17bd5cae534fb666"><td class="memSeparator" colspan="2">&#160;</td></tr>
<tr class="memitem:a563e87041fc859e7bafe4a11a790dec2"><td class="memTemplParams" colspan="2">template&lt;typename T &gt; </td></tr>
<tr class="memitem:a563e87041fc859e7bafe4a11a790dec2"><td class="memTemplItemLeft" align="right" valign="top">T&#160;</td><td class="memTemplItemRight" valign="bottom"><a class="el" href="namespace_introduction_to_algorithm_1_1_sort_algorithm.html#a563e87041fc859e7bafe4a11a790dec2">digi_on_N</a> (T num, std::size_t n)</td></tr>
<tr class="memdesc:a563e87041fc859e7bafe4a11a790dec2"><td class="mdescLeft">&#160;</td><td class="mdescRight">digi_on_N ： 获取正整数指定位数上的数字  <a href="#a563e87041fc859e7bafe4a11a790dec2">More...</a><br /></td></tr>
<tr class="separator:a563e87041fc859e7bafe4a11a790dec2"><td class="memSeparator" colspan="2">&#160;</td></tr>
<tr class="memitem:ad16d57510168e93b3d7439bf8ba48352"><td class="memTemplParams" colspan="2">template&lt;typename Iterator &gt; </td></tr>
<tr class="memitem:ad16d57510168e93b3d7439bf8ba48352"><td class="memTemplItemLeft" align="right" valign="top">void&#160;</td><td class="memTemplItemRight" valign="bottom"><a class="el" href="namespace_introduction_to_algorithm_1_1_sort_algorithm.html#ad16d57510168e93b3d7439bf8ba48352">radix_sort</a> (const Iterator begin, const Iterator end, std::size_t radix_width)</td></tr>
<tr class="memdesc:ad16d57510168e93b3d7439bf8ba48352"><td class="mdescLeft">&#160;</td><td class="mdescRight">radix_sort：算法导论第8章 8.3  <a href="#ad16d57510168e93b3d7439bf8ba48352">More...</a><br /></td></tr>
<tr class="separator:ad16d57510168e93b3d7439bf8ba48352"><td class="memSeparator" colspan="2">&#160;</td></tr>
</table>
<a name="details" id="details"></a><h2 class="groupheader">Detailed Description</h2>
<div class="textblock"><p>Namespace of <a class="el" href="namespace_introduction_to_algorithm_1_1_sort_algorithm.html" title="Namespace of SortAlgorithm. ">SortAlgorithm</a>. </p>
<p>该命名空间内包含所有排序算法 </p>
</div><h2 class="groupheader">Function Documentation</h2>
<a class="anchor" id="a1c3f0138b22c1e0c0bbfa67490ec51f1"></a>
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template&lt;typename Iterator &gt; </div>
      <table class="memname">
        <tr>
          <td class="memname">void IntroductionToAlgorithm::SortAlgorithm::bucket_sort </td>
          <td>(</td>
          <td class="paramtype">const Iterator&#160;</td>
          <td class="paramname"><em>begin</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype">const Iterator&#160;</td>
          <td class="paramname"><em>end</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype">const typename std::iterator_traits&lt; Iterator &gt;::value_type &amp;&#160;</td>
          <td class="paramname"><em>min_val</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype">const typename std::iterator_traits&lt; Iterator &gt;::value_type &amp;&#160;</td>
          <td class="paramname"><em>max_val</em>&#160;</td>
        </tr>
        <tr>
          <td></td>
          <td>)</td>
          <td></td><td></td>
        </tr>
      </table>
</div><div class="memdoc">

<p>bucket_sort：算法导论第8章 8.4 </p>
<dl class="params"><dt>Parameters</dt><dd>
  <table class="params">
    <tr><td class="paramname">begin</td><td>: 待排序序列的起始迭代器（也可以是指向数组中某元素的指针） </td></tr>
    <tr><td class="paramname">end</td><td>待排序序列的终止迭代器（也可以是指向数组中某元素的指针） </td></tr>
    <tr><td class="paramname">min_val:待排序序列元素的下界（不一定是最紧下界）</td><td></td></tr>
    <tr><td class="paramname">max_val:待排序序列元素的上界（不一定是最紧上界）</td><td></td></tr>
  </table>
  </dd>
</dl>
<dl class="section return"><dt>Returns</dt><dd>void</dd></dl>
<ul>
<li>桶排序思想，假设对数组A[p...r]排序，首先将这些元素进行hash运算，根据其hash值放入桶的对应区间中；然后对每一个区间中的元素进行排序；最后合并桶中各区间排序好的结果得到排序的数据：<ul>
<li>hash算法必须满足：若 a&lt;b ，则hash(a)&lt;hash(b)</li>
<li>要求 hash的结果尽量好，使得各数据平均分布在各区间内</li>
</ul>
</li>
<li>期望时间复杂度 O(n)</li>
<li>非原地排序 </li>
</ul>

<p>Definition at line <a class="el" href="bucketsort_8h_source.html#l00043">43</a> of file <a class="el" href="bucketsort_8h_source.html">bucketsort.h</a>.</p>

</div>
</div>
<a class="anchor" id="af51ff6ca75d6dccb1add1ad92a5d32fb"></a>
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template&lt;typename Iterator &gt; </div>
      <table class="memname">
        <tr>
          <td class="memname">void IntroductionToAlgorithm::SortAlgorithm::count_sort </td>
          <td>(</td>
          <td class="paramtype">const Iterator&#160;</td>
          <td class="paramname"><em>begin</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype">const Iterator&#160;</td>
          <td class="paramname"><em>end</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype">const typename std::iterator_traits&lt; Iterator &gt;::value_type &amp;&#160;</td>
          <td class="paramname"><em>max_val</em>&#160;</td>
        </tr>
        <tr>
          <td></td>
          <td>)</td>
          <td></td><td></td>
        </tr>
      </table>
</div><div class="memdoc">

<p>count_sort：算法导论第8章 8.2 </p>
<dl class="params"><dt>Parameters</dt><dd>
  <table class="params">
    <tr><td class="paramname">begin</td><td>: 待排序序列的起始迭代器（也可以是指向数组中某元素的指针） </td></tr>
    <tr><td class="paramname">end</td><td>待排序序列的终止迭代器（也可以是指向数组中某元素的指针） </td></tr>
    <tr><td class="paramname">max_val:待排序序列的元素值的上界（不一定是最紧的上界）</td><td></td></tr>
  </table>
  </dd>
</dl>
<dl class="section return"><dt>Returns</dt><dd>void</dd></dl>
<ul>
<li>计数排序思想，假设对数组A[p...r]排序，其中数组中所有元素都为正整数，并且都是小于max_val：<ul>
<li>首先对A进行计数。对每一个元素A[i]，将它出现的次数存放在CounterArray[A[i]]中</li>
<li>然后对CounterArray累加，得出A[i]应该在结果序列中排多少位</li>
<li>最后在结果数组中直接放置A[i]（根据它的排位）</li>
</ul>
</li>
<li>时间复杂度 O(n)</li>
<li>空间复杂度 O(n)</li>
</ul>
<p>&gt;这里必须对整数才能采取计数排序。由static_assert(...,...)确保 </p>

<p>Definition at line <a class="el" href="countsort_8h_source.html#l00045">45</a> of file <a class="el" href="countsort_8h_source.html">countsort.h</a>.</p>

</div>
</div>
<a class="anchor" id="a563e87041fc859e7bafe4a11a790dec2"></a>
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template&lt;typename T &gt; </div>
      <table class="memname">
        <tr>
          <td class="memname">T IntroductionToAlgorithm::SortAlgorithm::digi_on_N </td>
          <td>(</td>
          <td class="paramtype">T&#160;</td>
          <td class="paramname"><em>num</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype">std::size_t&#160;</td>
          <td class="paramname"><em>n</em>&#160;</td>
        </tr>
        <tr>
          <td></td>
          <td>)</td>
          <td></td><td></td>
        </tr>
      </table>
</div><div class="memdoc">

<p>digi_on_N ： 获取正整数指定位数上的数字 </p>
<dl class="params"><dt>Parameters</dt><dd>
  <table class="params">
    <tr><td class="paramname">num</td><td>: 待抽取数字的正整数 </td></tr>
    <tr><td class="paramname">n</td><td>指定的位数（0表示个位，1表示十位，...） </td></tr>
  </table>
  </dd>
</dl>
<dl class="section return"><dt>Returns</dt><dd>指定正整数指定位数上的数字</dd></dl>
<p>这里采用的 T 必须为某个整数类型，由static_assert(std::is_integral&lt;T&gt;::value,"..."")确保 </p>

<p>Definition at line <a class="el" href="radixsort_8h_source.html#l00039">39</a> of file <a class="el" href="radixsort_8h_source.html">radixsort.h</a>.</p>

</div>
</div>
<a class="anchor" id="a363c47d6d0dad2f1217b08d355e81126"></a>
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template&lt;typename Iterator , typename CompareType  = std::less&lt;typename std::iterator_traits&lt;Iterator&gt;::value_type&gt;&gt; </div>
      <table class="memname">
        <tr>
          <td class="memname">void IntroductionToAlgorithm::SortAlgorithm::insert_sort </td>
          <td>(</td>
          <td class="paramtype">const Iterator&#160;</td>
          <td class="paramname"><em>begin</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype">const Iterator&#160;</td>
          <td class="paramname"><em>end</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype">CompareType&#160;</td>
          <td class="paramname"><em>compare</em> = <code>CompareType()</code>&#160;</td>
        </tr>
        <tr>
          <td></td>
          <td>)</td>
          <td></td><td></td>
        </tr>
      </table>
</div><div class="memdoc">

<p>insert_sort：算法导论第二章 2.1 </p>
<dl class="params"><dt>Parameters</dt><dd>
  <table class="params">
    <tr><td class="paramname">begin</td><td>: 待排序序列的起始迭代器（也可以是指向数组中某元素的指针） </td></tr>
    <tr><td class="paramname">end</td><td>待排序序列的终止迭代器（也可以是指向数组中某元素的指针） </td></tr>
    <tr><td class="paramname">compare</td><td>一个可调用对象，可用于比较两个对象的小于比较，默认为std::less&lt;T&gt; </td></tr>
  </table>
  </dd>
</dl>
<dl class="section return"><dt>Returns</dt><dd>void</dd></dl>
<ul>
<li>插入排序思想，假设对数组A[p...r]排序：<ul>
<li>维持不变式：设当前排序的元素是 A[q]，则保持A[p...q-1]为排好的，A[q]在A[p...q-1]中找到它的位置坐下</li>
</ul>
</li>
<li>时间复杂度 O(n^2)</li>
<li>原地排序 </li>
</ul>

<p>Definition at line <a class="el" href="insertsort_8h_source.html#l00038">38</a> of file <a class="el" href="insertsort_8h_source.html">insertsort.h</a>.</p>

</div>
</div>
<a class="anchor" id="a4806cf41bd25ff1d1344d858a7a5b577"></a>
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template&lt;typename Iterator , typename CompareType  = std::less&lt;typename std::iterator_traits&lt;Iterator&gt;::value_type&gt;&gt; </div>
      <table class="memname">
        <tr>
          <td class="memname">void IntroductionToAlgorithm::SortAlgorithm::merge </td>
          <td>(</td>
          <td class="paramtype">const Iterator&#160;</td>
          <td class="paramname"><em>begin</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype">const Iterator&#160;</td>
          <td class="paramname"><em>end</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype">const Iterator&#160;</td>
          <td class="paramname"><em>middle</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype">CompareType&#160;</td>
          <td class="paramname"><em>compare</em> = <code>CompareType()</code>&#160;</td>
        </tr>
        <tr>
          <td></td>
          <td>)</td>
          <td></td><td></td>
        </tr>
      </table>
</div><div class="memdoc">

<p>merge：算法导论第二章 2.3.1 </p>
<dl class="params"><dt>Parameters</dt><dd>
  <table class="params">
    <tr><td class="paramname">begin</td><td>: begin...middle之间为已排好序列 </td></tr>
    <tr><td class="paramname">end</td><td>middle...end之间为已排好序列 </td></tr>
    <tr><td class="paramname">middle</td><td>begin...middle之间为已排好序列 </td></tr>
    <tr><td class="paramname">compare</td><td>一个可调用对象，可用于比较两个对象的小于比较，默认为std::less&lt;T&gt; </td></tr>
  </table>
  </dd>
</dl>
<dl class="section return"><dt>Returns</dt><dd>void</dd></dl>
<ul>
<li>归并思想，假设对数组A[p...q...r]归并：<ul>
<li>拷贝：将数组A[p...q]拷贝到数组L，将数组A[q...r]拷贝到数组R，</li>
<li>归并： 从左到右依次取L、R中的较小的元素，存放到A中（具体算法见代码）</li>
</ul>
</li>
<li>时间复杂度 O(n)</li>
<li>归并时需要额外的空间 O(n) </li>
</ul>

<p>Definition at line <a class="el" href="mergesort_8h_source.html#l00042">42</a> of file <a class="el" href="mergesort_8h_source.html">mergesort.h</a>.</p>

</div>
</div>
<a class="anchor" id="a38dce6f6996c858aef1096d75bb785db"></a>
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template&lt;typename Iterator , typename CompareType  = std::less&lt;typename std::iterator_traits&lt;Iterator&gt;::value_type&gt;&gt; </div>
      <table class="memname">
        <tr>
          <td class="memname">void IntroductionToAlgorithm::SortAlgorithm::merge_sort </td>
          <td>(</td>
          <td class="paramtype">const Iterator&#160;</td>
          <td class="paramname"><em>begin</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype">const Iterator&#160;</td>
          <td class="paramname"><em>end</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype">CompareType&#160;</td>
          <td class="paramname"><em>compare</em> = <code>CompareType()</code>&#160;</td>
        </tr>
        <tr>
          <td></td>
          <td>)</td>
          <td></td><td></td>
        </tr>
      </table>
</div><div class="memdoc">

<p>merge_sort：算法导论第二章 2.3.1 </p>
<dl class="params"><dt>Parameters</dt><dd>
  <table class="params">
    <tr><td class="paramname">begin</td><td>: 待排序序列的起始迭代器（也可以是指向数组中某元素的指针） </td></tr>
    <tr><td class="paramname">end</td><td>待排序序列的终止迭代器（也可以是指向数组中某元素的指针） </td></tr>
    <tr><td class="paramname">compare</td><td>一个可调用对象，可用于比较两个对象的小于比较，默认为std::less&lt;T&gt; </td></tr>
  </table>
  </dd>
</dl>
<dl class="section return"><dt>Returns</dt><dd>void</dd></dl>
<ul>
<li>归并排序思想，假设对数组A[p...r]排序：<ul>
<li>分解：将数组A[p...r]平均划分为2子数组A[p...q-1]个A[q...r]，一直划分直到每个子数组只有1个元素</li>
<li>归并： 对 A[p...q-1]和A[q...r]这两个已排序好的数组进行合并</li>
</ul>
</li>
<li>时间复杂度 O(nlgn)</li>
<li>非原地排序，归并时需要额外的空间 O(n) </li>
</ul>

<p>Definition at line <a class="el" href="mergesort_8h_source.html#l00086">86</a> of file <a class="el" href="mergesort_8h_source.html">mergesort.h</a>.</p>

</div>
</div>
<a class="anchor" id="a3a2d13a83cd168d9a10df0ed8c39f9ee"></a>
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template&lt;typename Iterator , typename CompareType  = std::less&lt;typename std::iterator_traits&lt;Iterator&gt;::value_type&gt;&gt; </div>
      <table class="memname">
        <tr>
          <td class="memname">Iterator IntroductionToAlgorithm::SortAlgorithm::partition </td>
          <td>(</td>
          <td class="paramtype">const Iterator&#160;</td>
          <td class="paramname"><em>begin</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype">const Iterator&#160;</td>
          <td class="paramname"><em>end</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype">const Iterator&#160;</td>
          <td class="paramname"><em>partition_iter</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype">CompareType&#160;</td>
          <td class="paramname"><em>compare</em> = <code>CompareType()</code>&#160;</td>
        </tr>
        <tr>
          <td></td>
          <td>)</td>
          <td></td><td></td>
        </tr>
      </table>
</div><div class="memdoc">

<p>partition： 算法导论第7章快速排序中的划分算法 </p>
<dl class="params"><dt>Parameters</dt><dd>
  <table class="params">
    <tr><td class="paramname">begin</td><td>: 待划分序列的起始迭代器（也可以是指向数组中某元素的指针） </td></tr>
    <tr><td class="paramname">end</td><td>待划分序列的终止迭代器（也可以是指向数组中某元素的指针） </td></tr>
    <tr><td class="paramname">partition_iter</td><td>指定划分元素的对应的迭代器（也可以是指向数组中某元素的指针） </td></tr>
    <tr><td class="paramname">compare</td><td>一个可调用对象，可用于比较两个对象的小于比较，默认为std::less&lt;T&gt; </td></tr>
  </table>
  </dd>
</dl>
<dl class="section return"><dt>Returns</dt><dd>:划分之后该划分元素值在序列中对应的新迭代器（也可以是指向数组中某元素的指针）</dd></dl>
<ul>
<li>划分思想，假设对数组A[p...r]划分，划分主元为A[q]：<ul>
<li>交换：首先将A[q]与A[r]交换，使得新的A[r]成为划分元素</li>
<li>循环：维持循环不变式： A[p...smaller_next-1]始终小于A[r]，A[smaller_next...current-1]始终大于A[r]。开始对A[current]进行判别：<ul>
<li>若A[current]&lt;A[r] 则交换 A[current]与 A[smaller_next], current右移（进行下一个元素的判断），smaller_next右移（维持不变式）</li>
<li>若A[current]&gt;=A[r], current右移（进行下一个元素的判断）</li>
</ul>
</li>
</ul>
</li>
<li>时间复杂度 O(n)</li>
<li>原地操作 </li>
</ul>

<p>Definition at line <a class="el" href="quicksort_8h_source.html#l00043">43</a> of file <a class="el" href="quicksort_8h_source.html">quicksort.h</a>.</p>

</div>
</div>
<a class="anchor" id="aa304e98b87d7ec1c17bd5cae534fb666"></a>
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template&lt;typename Iterator , typename CompareType  = std::less&lt;typename std::iterator_traits&lt;Iterator&gt;::value_type&gt;&gt; </div>
      <table class="memname">
        <tr>
          <td class="memname">void IntroductionToAlgorithm::SortAlgorithm::quick_sort </td>
          <td>(</td>
          <td class="paramtype">const Iterator&#160;</td>
          <td class="paramname"><em>begin</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype">const Iterator&#160;</td>
          <td class="paramname"><em>end</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype">CompareType&#160;</td>
          <td class="paramname"><em>compare</em> = <code>CompareType()</code>&#160;</td>
        </tr>
        <tr>
          <td></td>
          <td>)</td>
          <td></td><td></td>
        </tr>
      </table>
</div><div class="memdoc">

<p>quick_sort： 算法导论第7章 </p>
<dl class="params"><dt>Parameters</dt><dd>
  <table class="params">
    <tr><td class="paramname">begin</td><td>: 待排序序列的起始迭代器（也可以是指向数组中某元素的指针） </td></tr>
    <tr><td class="paramname">end</td><td>待排序序列的终止迭代器（也可以是指向数组中某元素的指针） </td></tr>
    <tr><td class="paramname">compare</td><td>一个可调用对象，可用于比较两个对象的小于比较，默认为std::less&lt;T&gt; </td></tr>
  </table>
  </dd>
</dl>
<dl class="section return"><dt>Returns</dt><dd>void</dd></dl>
<ul>
<li>快速排序思想，假设对数组A[p...r]排序：<ul>
<li>分解：将数组A[p...r]划分为两个（可能为空）的子数组A[p...q-1]个A[q+1...r]，使得A[q]大于前面一个数组中每个元素，小于后面一个数组中每个元素（划分算法见partition算法）</li>
<li>解决： 对 A[p...q-1]和A[q+1...r]递归调用快速排序</li>
</ul>
</li>
<li>最坏时间复杂度 O(n^2)， 期望时间复杂度 O(nlgn)。它平均性能非常好，是实际排序应用中最好的选择</li>
<li>原地排序 </li>
</ul>

<p>Definition at line <a class="el" href="quicksort_8h_source.html#l00081">81</a> of file <a class="el" href="quicksort_8h_source.html">quicksort.h</a>.</p>

</div>
</div>
<a class="anchor" id="ad16d57510168e93b3d7439bf8ba48352"></a>
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template&lt;typename Iterator &gt; </div>
      <table class="memname">
        <tr>
          <td class="memname">void IntroductionToAlgorithm::SortAlgorithm::radix_sort </td>
          <td>(</td>
          <td class="paramtype">const Iterator&#160;</td>
          <td class="paramname"><em>begin</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype">const Iterator&#160;</td>
          <td class="paramname"><em>end</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype">std::size_t&#160;</td>
          <td class="paramname"><em>radix_width</em>&#160;</td>
        </tr>
        <tr>
          <td></td>
          <td>)</td>
          <td></td><td></td>
        </tr>
      </table>
</div><div class="memdoc">

<p>radix_sort：算法导论第8章 8.3 </p>
<dl class="params"><dt>Parameters</dt><dd>
  <table class="params">
    <tr><td class="paramname">begin</td><td>: 待排序序列的起始迭代器（也可以是指向数组中某元素的指针） </td></tr>
    <tr><td class="paramname">end</td><td>待排序序列的终止迭代器（也可以是指向数组中某元素的指针） </td></tr>
    <tr><td class="paramname">radix_width</td><td>待排序元素（必须是整数）的最大位宽，必须非0（由assert(radix_width!=0)确保） </td></tr>
  </table>
  </dd>
</dl>
<dl class="section return"><dt>Returns</dt><dd>void</dd></dl>
<ul>
<li>基数排序思想，假设对数组A[p...r]排序，其中数组中所有元素都为正整数，并且不超过RADIXWITH位（有模板的RADIXWITH参数指定）：<ul>
<li>首先对A中所有元素按照个位数大小进行排序（原地的）</li>
<li>再对A中所有元素按照个十数大小进行排序（原地的）</li>
<li>一直到最后按照A中所有元素的最高位的数字大小进行排序（原地的）</li>
</ul>
</li>
<li>时间复杂度 O(d(n+k))，其中d位数字的最大位宽(即这里都是d位数的整数），k为每个位数上数字取值（这里取0，1，2，3，...9）</li>
<li><p class="startli">原地排序</p>
<p class="startli">这里尤其要重点强调，用于对指定位上的数字进行排序时，必须要满足稳定性。</p><ul>
<li>快速排序就是非稳定的</li>
<li>用小于比较的插入排序是稳定的；用小于等于比较的插入排序是不稳定的</li>
</ul>
</li>
</ul>
<p>&gt;这里必须对整数才能采取基数排序。由static_assert(...,...)确保 </p>

<p>Definition at line <a class="el" href="radixsort_8h_source.html#l00067">67</a> of file <a class="el" href="radixsort_8h_source.html">radixsort.h</a>.</p>

</div>
</div>
</div><!-- contents -->
</div><!-- doc-content -->
<!-- start footer part -->
<div id="nav-path" class="navpath"><!-- id is needed for treeview function! -->
  <ul>
    <li class="navelem"><a class="el" href="namespace_introduction_to_algorithm.html">IntroductionToAlgorithm</a></li><li class="navelem"><a class="el" href="namespace_introduction_to_algorithm_1_1_sort_algorithm.html">SortAlgorithm</a></li>
    <li class="footer">Generated by
    <a href="http://www.doxygen.org/index.html">
    <img class="footer" src="doxygen.png" alt="doxygen"/></a> 1.8.10 </li>
  </ul>
</div>
</body>
</html>
